package demo2;

import demo1.ListNode;

import java.util.List;

public class Test2 {
    public boolean isPalindrome(ListNode head) {
        ListNode fast=head,slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        if(fast!=null)slow=slow.next;//处理奇数个节点
        slow=reverse(slow);
        fast=head;
        while(slow!=null){
            if(fast.val!=slow.val)return false;
            fast=fast.next;
            slow=slow.next;
        }
        return true;
    }
    private ListNode reverse(ListNode head){
        ListNode pre=null;
        while(head!=null){
            ListNode next=head.next;
            head.next=pre;
            pre=head;
            head=next;
        }
        return pre;
    }
        public static void main(String[] args) {
            Test2 test = new Test2();

            // 测试用例1: 回文链表 [1,2,2,1]
            ListNode head1 = new ListNode(1);
            head1.next = new ListNode(2);
            head1.next.next = new ListNode(2);
            head1.next.next.next = new ListNode(1);
            System.out.println("测试用例1 [1,2,2,1]: " + test.isPalindrome(head1)); // true

            // 测试用例2: 回文链表 [1,2,3,2,1]
            ListNode head2 = new ListNode(1);
            head2.next = new ListNode(2);
            head2.next.next = new ListNode(3);
            head2.next.next.next = new ListNode(2);
            head2.next.next.next.next = new ListNode(1);
            System.out.println("测试用例2 [1,2,3,2,1]: " + test.isPalindrome(head2)); // true

            // 测试用例3: 非回文链表 [1,2,3,4]
            ListNode head3 = new ListNode(1);
            head3.next = new ListNode(2);
            head3.next.next = new ListNode(3);
            head3.next.next.next = new ListNode(4);
            System.out.println("测试用例3 [1,2,3,4]: " + test.isPalindrome(head3)); // false

            // 测试用例4: 单个节点 [1]
            ListNode head4 = new ListNode(1);
            System.out.println("测试用例4 [1]: " + test.isPalindrome(head4)); // true

            // 测试用例5: 空链表
            System.out.println("测试用例5 []: " + test.isPalindrome(null)); // true

            // 测试用例6: 两个相同节点 [1,1]
            ListNode head6 = new ListNode(1);
            head6.next = new ListNode(1);
            System.out.println("测试用例6 [1,1]: " + test.isPalindrome(head6)); // true

            // 测试用例7: 两个不同节点 [1,2]
            ListNode head7 = new ListNode(1);
            head7.next = new ListNode(2);
            System.out.println("测试用例7 [1,2]: " + test.isPalindrome(head7)); // false
    }
}
